#include<iostream>
using namespace std;
//#include"InfoFile.h"
#include<stack>
class Solution {
public:
    string addBinary(string a, string b) {
        int N1 = a.length();
        int N2 = b.length();
        int i = N1 - 1;
        int j = N2 - 1;
        int carry = 0;
        stack<char>help;

        while (i >= 0 && j >= 0) {
            char tmp = addFunc(a[i], b[j]);
            if (carry) {
                if (tmp == '2') {
                    carry = 1;
                    help.push('1');
                }
                if (tmp == '1') {
                    carry = 1;
                    help.push('0');
                }
                if (tmp == '0') {
                    carry = 0;
                    help.push('1');
                }
            }
            else {
                if (tmp == '2') {
                    carry = 1;
                    help.push('0');
                }
                else {
                    carry = 0;
                    help.push(tmp);
                }
            }
            --i;
            --j;
        }
        while (i >= 0) {
            if (carry) {
                if (addFunc(a[i], '1') == '2') {
                    carry = 1;
                    help.push('0');
                }
                else {
                    carry = 0;
                    help.push(addFunc(a[i], '1'));
                }
            }
            else {
                help.push(a[i]);
            }
            --i;
        }
        while (j >= 0) {
            if (carry) {
                if (addFunc(b[j], '1') == '2') {
                    carry = 1;
                    help.push('0');
                }
                else {
                    carry = 0;
                    help.push(addFunc(b[j], '1'));
                }
            }
            else {
                help.push(b[j]);
            }
            --j;
        }
        if (carry) {
            help.push('1');
        }
        string str = "";
        while (!help.empty()) {
            char tmp = help.top();
            help.pop();
            str += tmp;
        }
        return str;
    }


    char addFunc(char a, char b) {
        if (a == '0') {
            if (b == '0') {
                return '0';
            }
            else if (b == '1') {
                return '1';
            }
        }
        if (a == '1') {
            if (b == '0') {
                return '1';
            }
            else if (b == '1') {
                return '2';
            }
        }
        return '2';
    }
};

void main() {

    Solution s;
    cout << s.addBinary("11"
        , "1001") << endl;
	system("pause");
}